package sort;

public class Quick3waySort {


    public static void sort(int[] arr){
        sort(arr,0, arr.length-1);
    }

    private static void sort(int[] arr, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;
        int v = arr[lo];
        while (i <= gt) {
            int temp = 0;
            if (arr[i] < v) {
                temp = arr[i];
                arr[i] = arr[lt];
                arr[lt] = temp;
                lt++;
                i++;
            } else if (arr[i] > v) {
                temp = arr[i];
                arr[i] = arr[gt];
                arr[gt] = temp;
                gt--;
            } else {
                i++;
            }
        }
        sort(arr, lo, lt - 1);
        sort(arr, gt + 1, hi);
    }
}
